#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.


"""
https://www.lintcode.com/problem/reverse-pairs/description
"""


class Solution:
    """
    @param A: an array
    @return: total of reverse pairs
    """
    def reversePairs(self, A):
        # return self.method1(A)
        # return self.method2(A)
        return self.method3(A)

    # ------------------- method1 ---------------------
    def method1(self, A):
        # write your code here
        # res = []
        cnt = 0
        for i in range(len(A)-1):
            for j in range(i+1, len(A)):
                if A[i] > A[j]:
                    cnt += 1

        return cnt

    # ------------------- method2 ---------------------
    def method2(self, A):
        if not A:
            return 0

        self.len = len(A)
        # base  = list(A)             #
        base  = [ (e, 0) for e in A]
        extra = self.len * [None]       # 辅助/extra

        self.mergesort_rec_of_method2(base, extra, 0, self.len)
        # print(base)
        return  sum( [e[1] for e in base] )

    def mergesort_rec_of_method2(self, base, extra, b_idx, e_idx):
        # [b, e) 开闭区间
        if e_idx - b_idx == 1:
            return

        mid_idx = (b_idx + e_idx) // 2
        self.mergesort_rec_of_method2(base, extra, b_idx, mid_idx)
        self.mergesort_rec_of_method2(base, extra, mid_idx, e_idx)

        left_idx = b_idx
        right_idx = mid_idx
        extra_idx = b_idx

        while left_idx < mid_idx and right_idx < e_idx:
            if base[left_idx][0] <= base[right_idx][0]:
                hit = left_idx
                inversion = base[left_idx][1]
                left_idx += 1
            else:
                hit = right_idx
                # inversion = base[left_idx][1] + base[right_idx][1] + 1      # 加的1是right_idx
                inversion = base[right_idx][1] + (mid_idx-left_idx)
                right_idx += 1
            extra[extra_idx] = base[hit][0], inversion
            extra_idx += 1

        if left_idx == mid_idx:
            extra[extra_idx:e_idx] = base[right_idx:e_idx]
        else:
            extra[extra_idx:e_idx] = base[left_idx:mid_idx]

        # copy to base
        base[b_idx:e_idx] = extra[b_idx:e_idx]

    # ------------------- method3 ---------------------
    def method3(self, A):
        if not A:
            return 0

        self.len = len(A)
        # base  = list(A)             #
        # base  = [ (e, 0) for e in A]
        base  = list(A)
        extra = self.len * [None]       # 辅助/extra

        return self.mergesort_rec_of_method3(base, extra, 0, self.len)
        # print(base)
        # return  sum( [e[1] for e in base] )

    def mergesort_rec_of_method3(self, base, extra, b_idx, e_idx):
        # [b, e) 开闭区间
        if e_idx - b_idx == 1:
            return 0

        # total = 0

        mid_idx = (b_idx + e_idx) // 2
        part1 = self.mergesort_rec_of_method3(base, extra, b_idx, mid_idx)
        part2 = self.mergesort_rec_of_method3(base, extra, mid_idx, e_idx)

        total = part1 + part2

        left_idx = b_idx
        right_idx = mid_idx
        extra_idx = b_idx

        while left_idx < mid_idx and right_idx < e_idx:
            if base[left_idx] <= base[right_idx]:
                hit = left_idx
                # inversion = base[left_idx][1]
                left_idx += 1
            else:
                hit = right_idx
                # inversion = base[left_idx][1] + base[right_idx][1] + 1      # 加的1是right_idx
                # inversion = base[right_idx][1] + (mid_idx-left_idx)
                right_idx += 1
                total += mid_idx-left_idx
            extra[extra_idx] = base[hit]
            extra_idx += 1

        if left_idx == mid_idx:
            extra[extra_idx:e_idx] = base[right_idx:e_idx]
        else:
            extra[extra_idx:e_idx] = base[left_idx:mid_idx]

        # copy to base
        base[b_idx:e_idx] = extra[b_idx:e_idx]
        return total


def test():
    s = Solution()

    # lst = [2, 4, 1, 3, 5, -1, 8, 5, 6, 99, 101, 87]
    # lst = [2, 4, 1, 3, 5, -1]

    lst = [4, 3, 2, 1]
    assert s.reversePairs(lst) == 6

    lst = [2, 4, 1, 3, 5]
    assert s.reversePairs(lst) == 3

    lst = [1, 2, 3, 4]
    assert s.reversePairs(lst) == 0

    lst = []
    assert s.reversePairs(lst) == 0

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
